package heap.medium;

import java.util.PriorityQueue;

/**
 * 有序矩阵中第 K 小的元素
 * 示例 1：
 *
 * 输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
 * 输出：13
 * 解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13
 * 示例 2：
 *
 * 输入：matrix = [[-5]], k = 1
 * 输出：-5
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix
 */
public class KthSmallestElementInASortedMatrix_378 {

    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        for (int[] ints : matrix) {
            maxHeap.offer(ints[0]);
            if (k < maxHeap.size())
                maxHeap.poll();
        }

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                maxHeap.offer(matrix[i][j]);
                if (k < maxHeap.size())
                    maxHeap.poll();
            }
        }
        return maxHeap.peek();
    }

    public static void main(String[] args) {
        KthSmallestElementInASortedMatrix_378 ks = new KthSmallestElementInASortedMatrix_378();
        System.out.println(ks.kthSmallest(new int[][]{{1,2},{3, 3}}, 1));

    }
}
